Mathijsen jest wychowankiem drużyny Willem II Tilburg, w której to przeszedł wszystkie szczeble juniorskie aż do pierwszej drużyny. W Eredivisie zadebiutował 27 lutego1999 roku w meczu przeciwko FC Utrecht i był to wówczas jedyny jego mecz w sezonie 1998/1999. Regularnie w zespole Willem II Mathijsen zaczął grać dopiero 2 lata później – najczęściej na lewej obronie. Nie był zbyt wyróżniającym się obrońcą ligi. W drużynie z Tilburga grał do lata 2004 a wtedy to przeszedł do zaczynającego być jedną czołowych drużyn ligi, AZ Alkmaar. W AZ Alkmaar Mathijsen rozwinął się znakomicie i już teraz jest jednym z lepszych obrońców ligi, a w sezonie 2005/2006 znacząco pomógł zespołowi w wywalczeniu wicemistrzostwa Eredivisie. W latach 2006–2011 był piłkarzem Hamburger SV, z którym wystąpił w Lidze Mistrzów. W sezonu 2011/2012 był zawodnikiem Malagi, z którą podpisał 2-letni kontrakt.
W 2012 roku Mathijsen przeszedł do Feyenoordu. W 2015 roku rozwiązał z nim kontrakt.
